package 马踏棋盘骑士周游问题;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class 马踏棋盘骑士周游问题 {

	//以棋盘左上角为坐标0点
	//棋盘列数
	private static int X;
	//棋盘行数
	private static int Y;
	//创建数组，表示是否被访问
	private static boolean visited[];
	//创建标记，是否棋盘所有位置都被访问
	private static boolean finished;
	
	public static void main(String[] args) {
		//测试
		X = 8;
		Y = 8;
		int row = 0;
		int column = 0;
		int[][] chessboard = new int[Y][X];
		visited = new boolean[X * Y];
		
		//耗时
		//未优化 62782
		//优化 42
		long start = System.currentTimeMillis();
		traversalChessboard(chessboard, row, column, 1);
		long end = System.currentTimeMillis();
		System.out.println(end - start);
		
		//输出棋盘
		for (int i = 0; i < chessboard.length; i++) {
			for (int j = 0; j < chessboard[i].length; j++) {
				System.out.print(chessboard[i][j] + "\t");
			}
			System.out.println();
		}
	}
	
	/**
	 * 骑士周游算法
	 * @param chessboard 棋盘
	 * @param row 开始行，初始0
	 * @param column 开始列 ，初始0
	 * @param step 行走第几步，初始1
	 */
	public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
		//在棋盘标记目前第几步
		chessboard[row][column] = step;
		//走过的路，标记true，因为visited是一维数组，所以使用 (行-1)*列+列 表示位置，因为是从0开始，所以不减一，
		//二维转一维
		visited[row * X + column] = true;
		
		//获取下一步可以走的集合，注意 X 和 Y ，是以左上角为标准的，初始化时为（Y，X）
		ArrayList<Point> ps = next(new Point(column,row));
		
		//优化，排序
		sort(ps);
		
		//遍历ps
		while(!ps.isEmpty()) {
			//取出下一个可以走的位置
			Point p = ps.remove(0);
			//判断是否访问，注意和上面要对应
			if(!visited[p.y * X + p.x]) {
				//未访问，开始递归，从这点开始向四个方向找路，注意 row column
				traversalChessboard(chessboard, p.y, p.x, step + 1);
			}
		}
		
		//判断是否走完，step等于棋盘数，表示走完，否则表示此路不同，不走这步，置为0，返回上一步
		//finished表示马是否完成任务
		if(step < X * Y && !finished) {
			//这一步不能走完整个棋盘，撤销全部操作，返回上一步
			chessboard[row][column] = 0;
			visited[row * X + column] = false;
		}else {
			//否则，表示这一步可以走完，finished为true，在最后回溯时，可以通过
			finished = true;
		}
	}
	
	/**
	 * 根据当前位置（Point），计算马下一步能走那些位置（Point），结果放入ArrayList中，最多8个
	 * @param curPoint 代表当前点的位置
	 * @return
	 */
	public static ArrayList<Point> next(Point curPoint){
		
		//创建一个ArrayList，存放下一步结果
		ArrayList<Point> ps = new ArrayList<Point>();
		
		//创建一个Point，表示新的地址
		Point p = new Point();
		//判断马是否可以走5的位置，就是左上角，并且在不超出地图范围内
		if((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y-1) >= 0) {
			//符合就加入下一步，把这个地址加入备选
			ps.add(new Point(p));
		}
		//判断马是否可以走6的位置，就是左上角，且不超出地图范围内，因为日字型有横竖，每个方向2个点
		if((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y - 2) >= 0) {
			//符合就加入下一步，把这个地址加入备选
			ps.add(new Point(p));
		}
		//判断马是否可以走7的位置，此时边界是 X ，不是 0
		if((p.x = curPoint.x + 1) < X && (p.y = curPoint.y - 2) >= 0) {
			ps.add(new Point(p));
		}
		//判断马是否可以走0的位置，此时边界是 X ，不是 0
		if((p.x = curPoint.x + 2) < X && (p.y = curPoint.y - 1) >= 0) {
			ps.add(new Point(p));
		}
		//判断马是否可以走1的位置，此时边界是 Y ，不是 0
		if((p.x = curPoint.x + 2) < X && (p.y = curPoint.y + 1) < Y) {
			ps.add(new Point(p));
		}
		//判断马是否可以走2的位置，此时边界是 Y ，不是 0
		if((p.x = curPoint.x + 1) < X && (p.y = curPoint.y + 2) < Y) {
			ps.add(new Point(p));
		}
		//判断马是否可以走3的位置，此时边界是 0
		if((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y + 2) < Y) {
			ps.add(new Point(p));
		}
		//判断马是否可以走4的位置，此时边界是 0
		if((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y + 1) < Y) {
			ps.add(new Point(p));
		}
		
		return ps;
	}
	
	/**
	 * 根据下一步集合，找出下下一步所有可走集合的数目，进行非递减排序
	 * @param ps
	 * @return
	 */
	public static void sort(ArrayList<Point> ps) {
		//外部比较器
		ps.sort(new Comparator<Point>() {

			@Override
			public int compare(Point o1, Point o2) {
				//计算o1下一步集合数目
				int count1 = next(o1).size();
				//计算o2下一步集合数目
				int count2 = next(o2).size();
				//比较
//				if(count1 < count2) {
//					return -1;
//				}else if(count1 == count2) {
//					return 0;
//				}else {
//					return 1;
//				}
				return count1 - count2;
			}
		});
	}
	
}
